package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;

//两个结点的最近公共祖先
public class FindLCA {
    BinaryTreeNode LCA(BinaryTreeNode root,BinaryTreeNode node1,BinaryTreeNode node2){
        BinaryTreeNode left,right;
        if (root==null)
            return null;
        if (root==node1||root==node2)
            return root;
        left=LCA(root.getLeft(),node1,node2);
        right=LCA(root.getRight(),node1,node2);
        //1、只有left和right都不为空时（roots的左孩子是一个结点的祖先，右孩子是另一个结点的祖先），返回转换为第二种，最后返回公告结点
        //2、left、right一个为null，一个有值，代表root是一个结点的祖先（还没有找到公共祖先），返回这个有值的结点
        //第二种一直返回有值的结点，直到两个结点祖先为同一个，及转换为第一种情况
        return (left!=null&&right!=null)?root:(left!=null?left:right);
    }

        @Test
        public void test() {
            int[] A = {1, 2, 4, 5, 3, 6, 7};
            int[] B = {4, 2, 5, 1, 6, 3, 7};
            BuildBinaryTree buildBinaryTree = new BuildBinaryTree();
            BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B, A, 0, 6);
            LCA(root,root.getLeft().getLeft(),root.getRight().getRight());
        }


}
